package com.kaili.common.tsp.simple;

/**
 * 简单暴力TSP破解算法
 */
public class ForceSimpleTsp {
    /**
     *最佳长度
     */
    private double bestLength = 0;

    /**
     *最佳路径
     */
    private int[] bestTour;

    /**
     * 城市数量
     */
    private int cityNum;

    /**
     * 城市组成的数组
     */
    private int[] cityData;

    /**
     * 城市之间的距离矩阵
     */
    private double[][] distance;

    /**
     * 城市组合个数
     */
    private Long maxCount = 0l;

    public static void main(String[] args) {
        int n = 12;
        double[][] distance = new double[n][n];
        for(int i=0 ; i<n;i++){
            for(int j = 0 ;j<n;j++){
                if(i == j){
                    distance[i][j]=0d;
                }else{
                    distance[i][j]=i+j;
                }
            }
        }
//                double[][] distance = {	//各个节点之间路径长度的二维数组
//                {0d,1d,1d,1d},
//                {1d,0d,2d,1.4d},
//                {1d,2d,0d,1.4d},
//                {1d,1.4d,1.4d,0d}};

        Long start = System.currentTimeMillis();
        ForceSimpleTsp tsp = new ForceSimpleTsp();
        // 1.初始化
        tsp.init(distance);
        // 2.计算最短路径
        tsp.calc(tsp.getCityData(), 1, tsp.getCityNum());
        //3.输出最短路径
        System.out.println("最佳长度："+tsp.getBestLength());
        System.out.println("最佳路径："+tsp.getBestTourToString());
        System.out.println("遍历组合总数："+ tsp.getMaxCount());

        Long end = System.currentTimeMillis();
        System.out.println("共耗时:"+(end-start)/1000f);
    }

    /**
     * 初始化
     * @param distance
     */
    public void init(double[][] distance){
        // 1.初始化城市数量
        this.cityNum = distance.length;

        // 2.初始化城市组成的数组
        this.cityData = new int[this.cityNum+1];
        for(int i=0;i< this.cityData.length;i++){
            if(i == 0 || i== this.cityData.length-1){
                this.cityData[i]=0;
            }else{
                this.cityData[i]=i;
            }
        }

        // 3.初始化城市之间的距离矩阵
        this.distance = distance;
    }

    /**
     * 计算
     * @param data
     * @param start
     * @param end
     */
    public void calc(int[] data, int start, int end) {
        if (start == end - 1) {
            this.maxCount++;
            double len = getTourLength(data);
//            System.out.println(toString(data));
            if(this.bestLength==0 || len<this.bestLength){
                this.bestLength = len;
                this.bestTour = data.clone();
                System.out.println(this.bestLength+","+this.getBestTourToString());
            }
        } else {
            for (int i = start; i < end; i++) {
                swap(data, start, i);
                calc(data, start + 1, end);

                swap(data, start, i);
            }
        }
    }

    /**
     * 计算路径长度
     * @param str
     * @return
     */
    private double getTourLength(int[] tour){
        double len = 0d;
        for (int i = 0; i < tour.length-1; i++) {
            len += this.distance[tour[i]][tour[i+1]];
        }

        return len;
    }

    /**
     * 交换两个元素的位置
     * @param data
     * @param start
     * @param end
     */
    private void swap(int[] data, int start, int end) {
        if(start == end){
            return;
        }

        int tmp = data[start];
        data[start] = data[end];
        data[end] = tmp;
    }

    public double getBestLength() {
        return this.bestLength;
    }

    public String getBestTourToString() {
        StringBuilder sb = new StringBuilder();
        for(int i : this.bestTour){
            sb.append(i).append(",");
        }
        sb.deleteCharAt(sb.length()-1);

        return sb.toString();
    }

    public Long getMaxCount() {
        return this.maxCount;
    }

    public int getCityNum() {
        return this.cityNum;
    }

    public int[] getCityData() {
        return this.cityData;
    }
}